package org.ww.algorithm.tree;


public class BinarySortTreeDemo {

    public static void main(String[] args) {
        int arr[]=new int[]{7,3,10,12,5,1,9,0};
        BinarySortTree binarySortTree=new BinarySortTree();
        for(int i=0;i<arr.length;i++){
            binarySortTree.add(new BinaryNode(arr[i]));
        }
        System.out.println("删除节点之前");
        binarySortTree.indexOrder();
        binarySortTree.delete(7);
        System.out.println("删除节点之后");
        binarySortTree.indexOrder();
    }
}

class BinarySortTree{
    BinaryNode root;
    public void add(BinaryNode node){
        if(root!=null){
            root.addNode(node);
        }else{
            root=node;
        }
    }
    //查找目标节点
    public BinaryNode search(int value){
        if(root==null){
            return null;
        }else{
            return root.search(value);
        }
    }

    //查找目标节点的父节点
    public BinaryNode searchParent(int value){
        if(root==null){
            return null;
        }else{
            return root.searchParent(value);
        }
    }

    /**
     * 查找根节点最小的节点值，返回并删除
     * @param node
     * @return
     */
    public BinaryNode delRightMin(BinaryNode node){
        BinaryNode target=node;
        while(target.left!=null){
            target=target.left;
        }
        delete(target.value);
        return target;
    }
    //删除节点
    public void delete(int value){
        if(root==null){
            return ;
        }else{
            //查找目标节点
            BinaryNode targetNode = search(value);
            if(targetNode==null){
                return ;
            }
            //删除的是根节点
            if(root.left==null && root.right==null){
                root=null;
                return ;
            }
            //查找目标节点的父节点
            BinaryNode parentNode = searchParent(value);
            //1 删除的是叶子节点
            if(targetNode.left==null && targetNode.right==null){
                if(parentNode.left!=null && parentNode.left.value==value ){
                    parentNode.left=null;
                }else if( parentNode.right!=null && parentNode.right.value==value ){
                    parentNode.right=null;
                }
            }else if(targetNode.left!=null && targetNode.right!=null){
                //2 删除有两个子节点的树
                BinaryNode binaryNode = delRightMin(targetNode.right);
                targetNode.value=binaryNode.value;
            }else {

                //3 删除只有一个子节点的树
                if(targetNode.left!=null){
                    if(parentNode!=null){
                        if(parentNode.left.value==value){
                            parentNode.left=targetNode.left;
                        }else{
                            parentNode.right=targetNode.left;
                        }
                    }else {
                        root=targetNode.left;
                    }

                }else{
                    if(parentNode==null){
                        if(parentNode.left.value==value){
                            parentNode.left=targetNode.right;
                        }else{
                            parentNode.right=targetNode.right;
                        }
                    }else{
                        root=targetNode.right;
                    }
                }
            }
        }
    }

    public void indexOrder(){
        root.infixOrder();
    }
}
class BinaryNode{
    int value;
    BinaryNode left;
    BinaryNode right;

    public BinaryNode(int value) {
        this.value = value;
    }
    //查找要删除的目标节点
    public BinaryNode search(int value){
        if(this.value==value){
            return this;
        }else if(value < this.value){
            if(this.left==null){
                return null;
            }
            return this.left.search(value);
        }else{
            if(this.right==null){
                return null;
            }
            return this.right.search(value);
        }
    }

    //查找要删除节点的父节点
    public BinaryNode searchParent(int value){
        if((this.left!=null && this.left.value == value ) ||
                (this.right!=null && this.right.value==value )){
            return this;
        }else{
            if( this.left!=null && value<this.value ){
                return this.left.searchParent(value);
            }else if( this.right!=null && value>=this.value ){
                return this.right.searchParent(value);
            }else{
                return null;
            }
        }
    }


    //添加节点
    public void addNode(BinaryNode node){
        if(node==null){
            return;
        }
        if(node.value<this.value){
            if(this.left==null){
                this.left=node;
            }else{
                this.left.addNode(node);
            }
        }else{
            if(this.right==null){
                this.right=node;
            }else{
                this.right.addNode(node);
            }
        }
    }

    //中序遍历
    public void infixOrder(){
        if(this.left!=null){
            this.left.infixOrder();
        }
        System.out.println(this);
        if(this.right!=null){
            this.right.infixOrder();
        }
    }

    @Override
    public String toString() {
        return "BinaryNode{" +
                "value=" + value +
                '}';
    }
}
